package offerbook;

/**
 * 请实现一个函数，将一个字符串中的每个空格替换成“%20”。
 * 例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
 * 这是在网络编程中，URL若还有空格和#等可能会导致服务器无法获取正确的参数值。
 * 所以要进行编码，编码规则是 %ASCII码（该字符对应的ASCII码）
 *
 *
 * 思路1：在C/C++中，每次遇到一个空格，要把之后的所有字符往后移动3位，移动复杂度是O(N),遍历是O(N)，所以从前往后是O(N²)
 * 思路2：利用特性，每有一个空格，会导致整体字符扩大2个，先遍历一遍统计空格个数，
 * 然后把字符串扩到 str.length + 2*num(space)
 * 利用两个指针p1,p2，一个指向str最后一个字符，一个指向扩展后的字符串最后位置。二者都向前移动，
 * 当p1遇到空格，则p2就生成02%，否则
 * p2复制p1的内容。
 *
 * 从后往前的思想，使得时间复杂度是O(N)
 */
public class Code04_BackToPre {

    public String replaceSpace1(StringBuffer str) {
       return str.toString().replace(" ","%20");
    }
    public String replaceSpace2(StringBuffer str) {
        StringBuffer sb = new StringBuffer();
        for(int i=0; i<str.length(); i++){
            if(str.charAt(i) == ' '){
                sb.append("%20");
            }else{
                sb.append(str.charAt(i));
            }
        }
        return sb.toString();
    }
}
